package kaka 
{
	import flash.display.*;
	import flash.geom.*;
	import flash.utils.*;
	
	/**
	 * 四叉树
	 * @author StefanieKaka
	 */
	public final class QuadTree 
	{
		/// 构造函数
		public function QuadTree(rect : Rectangle) 
		{
			m_rect = rect;
			m_root = this;
			m_data = new Vector.<*>();
		}
		
///////////////////////////////////////////////////////////////////////////////////////////////////
// 公共域
///////////////////////////////////////////////////////////////////////////////////////////////////
		
		/**
		 * 创建四叉树
		 * @param	deep 创建四叉树的深度
		 */
		public function createChildren(deep : int) : void
		{
			if (deep == 1)
				return;
				
			const hw : Number = m_rect.width / 2;
			const hh : Number = m_rect.height / 2;
				
			m_childA = new QuadTree(new Rectangle(m_rect.x, m_rect.y, hw, hh));
			m_childB = new QuadTree(new Rectangle(m_rect.x + hw, m_rect.y, hw, hh));
			m_childC = new QuadTree(new Rectangle(m_rect.x, m_rect.y + hh, hw, hh));
			m_childD = new QuadTree(new Rectangle(m_rect.x + hw, m_rect.y + hh, hw, hh));
			
			m_childA.m_parent = m_childB.m_parent = m_childC.m_parent = m_childD.m_parent = this;
			m_childA.m_root = m_childB.m_root = m_childC.m_root = m_childD.m_root = m_root;
			
			m_childA.createChildren(deep - 1);
			m_childB.createChildren(deep - 1);
			m_childC.createChildren(deep - 1);
			m_childD.createChildren(deep - 1);
		}
		
		/**
		 * 以点添加数据.
		 * @param	v 添加数据
		 * @param	x 指定的 x 坐标
		 * @param	y 指定的 y 坐标
		 * @return 返回被添加 data 的 QuadTree 对象, 没有添加则返回 null.
		 */
		public function addPoint(v : *, x : Number, y : Number) : QuadTree
		{
			if (!isIn(x, y))
				return null;
				
			if (hasChildren)
			{
				// 这里方法很屌! 因为返回的值不是 Boolean 类型, 但是会做 Boolean 类型判断, 如果判断结果为 true, 则会返回 QuadTree 类型
				return m_childA.addPoint(v, x, y) || m_childB.addPoint(v, x, y) || m_childC.addPoint(v, x, y) || m_childD.addPoint(v, x, y);
			}
			else
			{
				m_data.push(v);
				return this;
			}
		}
		
		/**
		 * 以点删除数据, 坐标为 NaN 则会遍历查找.
		 * @param	v 删除数据
		 * @param	x 指定的 x 坐标
		 * @param	y 指定的 y 坐标
		 * @return 返回被删除 data 的 QuadTree 对象, 没有被删除返回 null.
		 */
		public function removePoint(v : *, x : Number = NaN, y : Number = NaN) : QuadTree
		{
			if (!isIn(x, y))
				return null;
				
			if (hasChildren)
			{
				return m_childA.removePoint(v, x, y) || m_childB.removePoint(v, x, y) || m_childC.removePoint(v, x, y) || m_childD.removePoint(v, x, y);
			}
			else
			{
				var idx : int = m_data.indexOf(v);
				if (idx != -1)
				{
					m_data.splice(idx, 1);
					return this;
				}
				else
				{
					return null;
				}
			}
		}
		
		/**
		 * 以矩形添加矩形.
		 * @param	v 添加数据
		 * @param	rect 指定的矩形
		 */
		public function addRect(v : *, rect : Rectangle) : void
		{
			if (!m_rect.intersects(rect))
				return;
			
			if (hasChildren)
			{
				// 不同的子节点区域可能会添加相同一个数据 v
				m_childA.addRect(v, rect);
				m_childB.addRect(v, rect);
				m_childC.addRect(v, rect);
				m_childD.addRect(v, rect);
			}
			else
			{
				m_data.push(v);
			}
		}
		
		/**
		 * 以矩形删除矩形
		 * @param	v 删除数据
		 * @param	rect 指定的矩形
		 */
		public function removeRect(v : *, rect : Rectangle) : void
		{
			if (!m_rect.intersects(rect))
				return;
				
			if (hasChildren)
			{
				// 因为不同的子节点区域可能会拥有相同的一个数据 v
				m_childA.removeRect(v, rect);
				m_childB.removeRect(v, rect);
				m_childC.removeRect(v, rect);
				m_childD.removeRect(v, rect);
			}
			else
			{
				var idx : int = m_data.indexOf(v);
				if (idx != -1)
				{
					m_data.splice(idx, 1);
				}
			}
		}
		
		/**
		 * 获得一个范围内的数据
		 * @param	rect 确定的范围
		 * @return 获得的数据
		 */
		public function getDataInRect(rect : Rectangle, isFilter : Boolean = false) : Vector.<*>
		{
			if (!m_rect.intersects(rect))
				return new Vector.<*>();
			
			var data : Vector.<*> = m_data.concat();
			if (hasChildren)
			{	
				if (isFilter)
				{
					var dict : Dictionary = new Dictionary();
					checkValue(dict, m_childA.getDataInRect(rect));
					checkValue(dict, m_childB.getDataInRect(rect));
					checkValue(dict, m_childC.getDataInRect(rect));
					checkValue(dict, m_childD.getDataInRect(rect));
					
					for each (var v : * in dict)
						data.push(v);
				}
				else
				{
					data = data.concat(m_childA.getDataInRect(rect));
					data = data.concat(m_childB.getDataInRect(rect));
					data = data.concat(m_childC.getDataInRect(rect));
					data = data.concat(m_childD.getDataInRect(rect));
				}	
			}
			
			return data;
		}
		
		/// 绘制图像
		public function draw(graphics : Graphics, color : uint = 0x000000) : void
		{
			graphics.lineStyle(0, color);
			graphics.drawRect(m_rect.x, m_rect.y, m_rect.width, m_rect.height);
			
			if (hasChildren)
			{
				color = color << 4 | 0x0000000F;
				m_childA.draw(graphics, color);
				m_childB.draw(graphics, color);
				m_childC.draw(graphics, color);
				m_childD.draw(graphics, color);
			}
		}
		
		/**
		 * 返回遍历信息字符串
		 * @return 遍历信息字符串
		 */
		public function order() : String
		{
			return dump(1);
		}
		
		public function toString() : String
		{
			return "[QuadTree: Length=" + m_data.length + "]";
		}

///////////////////////////////////////////////////////////////////////////////////////////////////
// 私有域
///////////////////////////////////////////////////////////////////////////////////////////////////

		/**
		 * 判断是否有子树
		 */
		private function get hasChildren() : Boolean
		{
			return m_childA != null && m_childB != null && m_childC != null && m_childD != null;
		}
		
		/**
		 * 判断坐标是否在界限内, 设为 NaN 则不做限制
		 * @param	x x 坐标
		 * @param	y y 坐标
		 * @return 在界限内 true, 否则 false
		 */
		private function isIn(x : Number, y : Number) : Boolean
		{
			return m_rect.contains(x, y) || isNaN(x) || isNaN(y);
		}

		/// 遍历树, 打印信息
		private function dump(depth : int) : String
		{
			// 首先打印出自身节点数据
			var str : String = "";
			for (var i : int = 1; i <= depth; ++i)
			{
				if (i == depth)
					str += "+----";
				else
					str += "|    ";
			}
			
			str += this.toString() + "\n";
			
			if (hasChildren)
			{
				str += m_childA.dump(depth + 1);
				str += m_childB.dump(depth + 1);
				str += m_childC.dump(depth + 1);
				str += m_childD.dump(depth + 1);
			}
			
			return str;
		}

		/// 检查 dict 是否已经含有 data 中的值, 如果含有, 那么将不再放入到 dict 中, 否则添加到 dict 中
		private function checkValue(dict : Dictionary, data : Vector.<*>) : void
		{
			for each (var v : * in data)
			{
				if (dict[v] == null)
					dict[v] = v;
			}
		}
		
		/*
		 * 子节点分布示例
		 * +---+---+
		 * | A | B |
		 * |---|---|
		 * | C | D |
		 * +---+---+
		 */
		private var m_childA	: QuadTree = null;
		private var m_childB	: QuadTree = null;
		private var m_childC	: QuadTree = null;
		private var m_childD	: QuadTree = null;
		private var m_parent	: QuadTree = null;
		private var m_root		: QuadTree = null;
		private var m_rect		: Rectangle = null;
		private var m_data		: Vector.<*> = null;
	}

}